/**
 * Top k entries in an n by n symmetric matrix of floats.
 *
 * Usage:
 * ... n k <matrix_bin
 * n: n > 0 is the size of the symmetric matrix to read.
 * k: k > 0 is the number entries to keep.
 * matrix_bin: see symmetric_matrix::write_binary
 *
 * Output:
 * i j M(i,j)
 * i j M(i,j)
 * ...
 * where i <= j, sorted descending by M.
 */
#include <algorithm>
#include <iostream>
#include <iterator>
#include "u1.h"
#include "symmetric_matrix.h"
#include "toplist.h"

using namespace std;

// Struct used to remember where the top values in the matrix are. 
struct entry_t {
  entry_t(size_t i, size_t j, float m) : i(i), j(j), m(m) { }
  size_t i, j;
  float m;
};

ostream &operator<<(ostream &os, const entry_t &e) {
  return os<<e.i<<' '<<e.j<<' '<<e.m;
}

// Compare entries by matrix value.
struct F_entry_greater {
  bool operator()(const entry_t &x, const entry_t &y) const {
    return x.m > y.m;
  }
};

int main(int argc, char **argv) {
  if (argc != 3) {
    TRACE<<"see comments for usage"<<endl;
    exit(EXIT_FAILURE);
  }
  int n_int = atoi(argv[1]);
  if (n_int <= 0) {
    TRACE<<"n = "<<n_int<<" not > 0"<<endl;
    exit(EXIT_FAILURE);
  }
  int k_int = atoi(argv[2]);
  if (k_int <= 0) {
    TRACE<<"k = "<<k_int<<" not > 0"<<endl;
    exit(EXIT_FAILURE);
  }

  size_t n = (size_t)n_int;
  size_t k = (size_t)k_int;
  symmetric_matrix<float> M(n);
  toplist<entry_t, F_entry_greater> top(k, F_entry_greater());

  TRACE<<"reading M matrix"<<endl;
  M.read_binary(cin);

  TRACE<<"scanning"<<endl;
  for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j <= i; ++j) {
      top.insert(entry_t(i,j,M(i,j)));
    }
  }

  TRACE<<"sorting"<<endl;
  sort(top.begin(), top.end(), F_entry_greater());

  TRACE<<"writing"<<endl;
  copy(top.begin(), top.end(), ostream_iterator<entry_t>(cout, "\n"));

  return EXIT_SUCCESS;
}

/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

